// 思路，是插入排序的高级版，按照一定间隔gap进行插入排序，然后逐步缩小间隔gap进行插入排序，直到间隔为1，对整个序列进行插入排序

function shellSort(arr) {
    let gap = Math.floor(arr.length / 2)
    while (gap > 0) {
        for (let i = 0; i < arr.length; i++) {
            let temp = arr[i]
            let j = i
            // j >= gap，别漏掉gap为1
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap]
                j -= gap
            }
            arr[j] = temp
        }
        gap = Math.floor(gap / 2)
    }
    return arr
}

// 希尔排序的时间复杂度受增量的影响，当其增量为（n /2, (n / 2) / 2， ... , 1）,平均时间复杂度接近On^1.3

let arr = [2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
console.log(shellSort(arr))